#include <iostream>
#include <vector>
using namespace std;


// version 1
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ret;
        //可以使用前缀乘积 + 后缀乘积
        int n = nums.size();
        vector<int> f(n, 1), g(n, 1);

        //计算前缀积(不包括本身)
        for(int i = 1; i < n; ++i){
            f[i] = f[i - 1] * nums[i - 1]; //上一次的前缀积(没有乘前一个数) * 前一个数
            //默认第一个数字为1
        }

        //计算后缀积(不包括本身)
        for(int i = n - 2; i >= 0; --i){
            g[i] = g[i + 1] * nums[i + 1];
        }

        //因为前缀积和后缀积都没有计算到本身这个位置，所以，前缀积 * 后缀积就是要的答案
        for(int i = 0; i < n; ++i){
            ret.push_back(f[i] * g[i]);
        }
        return ret;
    }
};